/**
 * 理论基础： [详解-bilibili](https://www.bilibili.com/video/BV1my4y1Z7jj/?vd_source=9b00fcff29c5075af223e6ef3ac2af43)
 * 1. 什么时候用：通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了
 * 2. 为什么用： 当栈是递增或递减的时候 （Tip-这个递增减方向指的是 从栈顶到栈底 ），当前元素入栈时，它旁边的人就是想找的目标元素了 （因为是单调的，符合条件的一定在栈顶）
 * 3. 怎么用：栈里存放的是数组的下标。当想比较大小时，通过下标 arr[i] 去获取真正的元素来比较大小
 * 4. 作用：存放之前遍历过的元素，方便当前元素和栈顶元素比较
*/
const tip = '看注释'

/**42. 接雨水
 * - 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */
export function trap(height: number[]): number {
    // 3.单调栈 - 这个解法就是按照行来计算雨水 - 有点不好理解，没懂。面试的时候写出双指针优化版吧
    let res = 0
    const stack: number[] = []//装着索引的单调栈
    stack[0] = 0
    for (let i = 1; i < height.length; i++) {
        while (stack.length !== 0 && height[i] > height[stack[stack.length - 1]]) {
            const topIndex = stack.pop()!;
            if (stack.length !== 0) {
                const h = Math.min(height[stack[stack.length - 1]], height[i]) - height[topIndex];
                const w = i - stack[stack.length - 1] - 1; // 注意减一，只求中间宽度
                res += h * w;
            }
        }
        stack.push(i)
    }
    return res

    // //2. 对暴力解法的优化 - 在暴力解法中，每次都要去找最高柱子，存在重复计算，可以先把这个计算好。
    // const length = height.length
    // /**每个元素左边最高的柱子大小 */
    // const leftMaxHeight: number[] = []
    // /**每个元素右边最高的柱子大小 */
    // const rightMaxHeight: number[] = []
    // //初始化
    // leftMaxHeight[0] = height[0];
    // rightMaxHeight[length - 1] = height[length - 1];

    // //取当前元素和左/右侧最大的，循环过后，每个元素都代表左/右侧最高的柱子大小
    // for (let i = 1; i < length; i++) {
    //     leftMaxHeight[i] = Math.max(height[i], leftMaxHeight[i - 1]);
    // }
    // for (let i = length - 2; i >= 0; i--) {
    //     rightMaxHeight[i] = Math.max(height[i], rightMaxHeight[i + 1]);
    // }


    // let res = 0
    // //然后正式计算的时候就不用再去二次遍历了
    // for (let i = 0; i < length; i++) {
    //     res += Math.min(leftMaxHeight[i], rightMaxHeight[i]) - height[i]
    // }

    // return res

    // //1. 暴力解法，计算每一列，往左往右找最高的一列，Math.min(leftMax, rightMax) - nowHeight  就是当前列能借到的雨水
    // let res = 0
    // //注意起止条件，因为第一个柱子和最后一个柱子接不到雨水
    // for (let i = 1; i < height.length - 1; i++) {
    //     const nowHeight = height[i];

    //     let leftMax = nowHeight
    //     let rightMax = nowHeight
    //     for (let left = i - 1; left >= 0; left--) {
    //         if (height[left] > leftMax) leftMax = height[left]
    //     }
    //     for (let right = i + 1; right < height.length; right++) {
    //         if (height[right] > rightMax) rightMax = height[right]
    //     }
    //     console.log(nowHeight, Math.min(leftMax, rightMax));

    //     res += Math.min(leftMax, rightMax) - nowHeight
    // }
    // return res

}

/**496. 下一个更大元素 I
 * - nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
 * - 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
 * - 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
 * - 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
 */
export function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
    //基本原理和 739. 每日温度 一样
    // 1是2的子集，找出1中元素在2中位置，然后在2中找该元素的下一个更大元素  tip: [4,1,2]  [1,3,4,2]， nums1中元素"1"，在nums2中的下一个更大元素是"3"
    const res = new Array(nums1.length).fill(-1)
    /**放入索引 */
    const stack: number[] = []
    /**num1中，元素和索引的位置关系 */
    const map = new Map(nums1.map((k, i) => [k, i])) //因为我们需要在res的指定位置赋值，所以需要知道索引
    for (let i = 0; i < nums2.length; i++) {
        let top = nums2[stack[stack.length - 1]]
        while (top != undefined && nums2[i] > top) {
            //当前元素比栈顶大时，记录res，再弹出栈顶元素 
            if (map.has(top)) { //这题需要数字在num1也出现过，才记录
                res[map.get(top)!] = nums2[i]
            }
            stack.pop()
            top = nums2[stack[stack.length - 1]]
        }
        stack.push(i)//比他小的弹出后，放入当前内容
    }
    return res
}

/**503. 下一个更大元素 II
 * - 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
 * - 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
 */
export function nextGreaterElements2(nums: number[]): number[] {
    const res = new Array(nums.length).fill(-1)
    if (nums.length === 0) return res;
    const stack: number[] = []
    //遍历nums.length * 2，模拟循环
    for (let i = 0; i < nums.length * 2; i++) {
        const realIndex = i % nums.length
        let topIndex = stack[stack.length - 1]
        //当前的元素比栈顶的元素大时，说明 栈顶元素 遇到了“下一个更大元素”，所以是   res[topIndex] = nums[realIndex] 
        while (nums[topIndex] !== undefined && nums[topIndex] < nums[realIndex]) {
            res[topIndex] = nums[realIndex]
            stack.pop()
            topIndex = stack[stack.length - 1]
        }
        stack.push(realIndex)
    }
    return res
}

/**739. 每日温度
 * - 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 */
export function dailyTemperatures(temperatures: number[]): number[] {
    /**单调栈
     * 栈按照递增顺序存放 （从栈顶往栈底的递增） （存放下标，而不是真正的元素）
     * 从左往右遍历，当发现当前元素比栈顶元素大时 ---> 栈顶元素那一天的 下一个更高温度 则是当前元素代表的天。 ---> 往res存入 nowIndex - topIndex 
     */
    const stack: number[] = []
    const res = new Array<number>(temperatures.length).fill(0)
    for (let i = 0; i < temperatures.length; i++) {
        let topIndex = stack[stack.length - 1]
        console.log('————————————');

        console.log('topIndex', topIndex, temperatures[topIndex], 'nowIndex', i, temperatures[i]);

        //当前元素比栈顶大时
        //这里使用while，而不是普通的if， 是因为当前元素可以连续的比多个栈顶元素大 （大了的时候，当前栈顶弹出，**继续比较下一个栈顶**，避免造成跳跃）
        while (topIndex != undefined && temperatures[i] > temperatures[topIndex]) {
            res[topIndex] = i - topIndex
            console.log('res', res);
            stack.pop()//弹出栈顶元素，因为它的结果已经计算完了 （放入res了，后续不会再改了，因为要求的是最近的）
            topIndex = stack[stack.length - 1]
        }
        stack.push(i)
        //这里不用排序，因为 “大了则栈顶出栈，小的进栈”，那么一定保证数组是单调递增的
        // stack.sort((a, b) => temperatures[b] - temperatures[a]) //从数组末尾(栈顶)往数组头部(栈底) 单调递增排序
        console.log('stack', stack);
    }
    return res


}

